今天的題單：

• Maximum Depth of Binary Tree

• Contains Duplicate

104. Maximum Depth of Binary Tree

思路：bottom-up 算法，比較左子樹和右子樹的深度，回傳最大值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return depth(root);
    }

    int depth(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        if (node->left == nullptr && node->right == nullptr) {
            return 1;
        }
        return max(depth(node->left), depth(node->right)) + 1;
    }
};

217. Contains Duplicate

思路 1：把數字全部丟進 set，如果 set 大小小於數字數量，表示有重複

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> unique_num;

        for (int& num : nums) {
            unique_num.insert(num);
        }

        if (unique_num.size() < nums.size()) {
            return true;
        } else {
            return false;
        }
    }
};

思路 2：用 hash table，有 collision 就 return false，不需要全部看完

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, bool> unique_num;

        for (int& num : nums) {
            if (unique_num.find(num) != unique_num.end()) {
                return true;
            } else {
                unique_num[num] = true;
            }
        }
        return false;
    }
};

time 和 space 都是 O(n)，但 hash table 會快一些。